% Автор: Сергей Копелиович
% Источник: CS-Center, осенний семестр 2013-2014

\begin{problem}{Уставший профессор}
{sleepgame.in}{sleepgame.out}
{1 секунда}{256 мегабайт}{}

Уставший профессор вечером играет в увлекательную игру.

Изначально на доске слева направо записаны целые числа $a_1, a_2, \dots, a_n$.
Пока не уснет, профессор каждую секунду смотрит на числа, видит,
что самое левое равно $x$, а самое правое равно $y$.
Если $x$ меньше, то профессор радуется, стирает слева $x$, а справа дописывает $(x + y) \mod 2^{30}$.
Иначе профессор очень расстаивается, стирает $y$, а слева дописывает $(y - x) \mod 2^{30}$.
Студенты подсчитали, что перед сном профессор успел сделать ровно $k$ операций.
Что было написано на доске, когда он наконец заснул?
Для простоты можно считать, что доска в обе стороны бесконечна.

\InputFile

На первой строке $n$ ($1 \le n \le 30\,000$) и $k$ ($1 \le k \le 10^8$).
На второй строке числа $a_1, a_2, \dots, a_n$ ($0 \le a_i < 10^9$) в порядке слева направо.

\OutputFile

На первой строке выведите все числа на доске после $k$ операций.
Выводить числа нужно в порядке слева направо.

\Examples

\begin{example}
\exmp{
4 1
1 2 3 4
}{
2 3 4 5
}%
\exmp{
4 1000
1 2 3 4
}{
1062488873 1072033429 1060433235 57573251
}%
\exmp{
4 1
4 3 2 1
}{
1073741821 4 3 2
}%
\exmp{
4 2
4 3 2 1
}{
5 1073741821 4 3
}%
\end{example}

\end{problem}
